package leetcode.code0889;

import java.util.Arrays;

import leetcode.helper.H;
import leetcode.helper.tree.TreeNode;

public class Solution {

	int[] preorder;
	int[] postorder;

	public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
		this.preorder = preorder;
		this.postorder = postorder;
		int len = preorder.length;
		return build(0, len - 1, 0, len - 1);
	}

	private TreeNode build(int L, int R, int l, int r) {
		if (L > R) {
			return null;
		}
		if (L == R) {
			return new TreeNode(this.preorder[L]);
		}
		TreeNode ans = new TreeNode(this.preorder[L]);
		int root = this.preorder[L + 1];
		int p = l;
		while (p <= r && this.postorder[p] != root) {
			p++;
		}
		int size = p - l;
		ans.left = this.build(L + 1, L + 1 + size, l, p);
		ans.right = this.build(L + 1 + size + 1, R, p + 1, r - 1);
		return ans;
	}
	
	public static void main(String[] args) {
		int[] nums = new int[] {0,1,2,3,4,5};
		H.print(Arrays.copyOfRange(nums,1,10));
	}
}
